#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
        pass


from linked_list_util import *


class Solution:
    def sortedListToBST(self, head):
        # write your code here
        cnt = len_linked_list(head)
        self.cur = head
        print(cnt)

        return self.rec_build(cnt)

    def rec_build(self, size):
        if size <= 0:
            return None

        left = self.rec_build(size // 2)

        root = TreeNode(self.cur.val)
        self.cur = self.cur.next

        root.left = left

        root.right = self.rec_build(size - size//2 - 1)
        return root


def main():
    print("start main")

    v5 = ListNode(10)
    v4 = ListNode(8, v5)
    v3 = ListNode(6, v4)
    v2 = ListNode(4, v3)
    v1 = ListNode(2, v2)
    vm = ListNode(1, v1)
    s = Solution()
    ret = s.sortedListToBST(vm)
    print(ret.val)


if __name__ == "__main__":
    main()
